#include "string_array.h"
using namespace std;

//构造函数：字符串初始化
myStr::myStr(const char* str)
{
    //单独处理空串的情况
    if(str==nullptr)
    {
        length=0;
        data=new char[1];
        data[0]='\0';//将字符串最后一位设为'\0'
        next=nullptr;
        nextVal=nullptr;
    }
    //str不为空串的情况
    else
    {
        length=0;
        while(str[length]!='\0')
        {
        length++;
        }
        data=new char[length+1];
        for(int i=0;i<=length;i++)
        {
        data[i]=str[i];
        }
        next=nullptr;
        nextVal=nullptr;
    }
}
//用长度来构造
myStr::myStr(const int& num)
{
    data=new char[num+1];
    length=num;
    data[num] = '\0';
    next=nullptr;
    nextVal=nullptr;
}

//拷贝构造函数
myStr::myStr(const myStr& other) {
    length = other.length;
    data =new char[length + 1];
    for(int i = 0; i <= length; i++) {
        data[i] = other.data[i];
    }
    next = nullptr; 
    nextVal = nullptr;
}

//赋值运算符重载
myStr& myStr::operator=(const myStr& other) {
    if (this == &other) return *this;
    delete[] data;
    length = other.length;
    data = new char[length + 1];
    for(int i = 0; i <= length; i++) {
        data[i] = other.data[i];
    }
    return *this;
}

//析构函数：字符串销毁，释放所有的动态内存
myStr::~myStr()
{
    delete[] data;
    delete[] next;
    delete[] nextVal;
}

//字符串输出
void myStr::print(){
    for(int i = 0; i < this->length; i++)
        cout << this->data[i];

    cout << endl;
}

//简单字符串匹配算法(BF)
int simpleMatch(const myStr& S, const myStr& T)
{
    if (T.length==0) return -1; 
    if (S.length==0) return -1;   
    if(T.length>S.length) return -1;
    int i=0,j=0;
    while(i<S.length&&j<T.length)
    {
        if(S.data[i]==T.data[j]) 
        {
            i++;
            j++;
        }
        else
        {
            i=i-j+1;
            j=0;
        }
    }
    if(j>=T.length) return i-T.length+1;
    else return -1;
}

//串的替换
bool replaceStr(myStr& S, const int& start, const myStr& T, const myStr& V)
{
   if (start<1||start>S.length) return false;
   int subLen=S.length-start + 1;
   myStr S1(subLen);
   for(int i=0;i<subLen;i++) {
    S1.data[i]=S.data[start-1+i];
   }
   int pos=simpleMatch(S1,T);
   if(pos<0) return 0;
   else
   {
    pos=pos+start-2;
    myStr result(S.length-T.length+V.length);
    //复制前段
    for(int i=0; i<pos; i++) {
        result.data[i]=S.data[i];
    }
    //复制V
    for(int i=0; i<V.length; i++) {
        result.data[pos+i]=V.data[i];
    }
    //复制后段
    for(int i=pos+T.length; i<S.length; i++) {
        result.data[i-T.length+V.length]=S.data[i];
    }
    S=result;
    return 1;
   }
}

//kmp辅助数组next的计算
void myStr::kmp_next()
{
    if(next!=nullptr) delete[] next;
    next=new int[length];
    next[0]=0;
    int i=0,j=0;
    while(i<length-1)
    {
        if(j==0||data[i]==data[j-1])
        {
            i++;
            j++;
            next[i]=j;
        }
        else
        {
            j=next[j-1];
        }
    }
}

//kmp辅助数组nextVal的计算
void myStr::kmp_nextVal()
{
    if(nextVal!=nullptr) delete[] nextVal;
    nextVal=new int[length];
    int i=0,j=0;
    nextVal[0]=0;
    while(i<length-1)
    {
        if(j==0||data[i]==data[j-1])
        {
            i++;
            j++;
            if(data[i]!=data[j-1]) nextVal[i]=j;
            else nextVal[i]=nextVal[j-1];
        }
        else j=nextVal[j-1];
    }
}

//改进KMP算法的字符串匹配算法
int kmpMatch(const myStr& S, const myStr& T)
{
    if (T.next==nullptr||T.length==0) return -1; 
    int i=0,j=0;
    while(i<S.length&&j<T.length)
    {
        if(j==0||S.data[i]==T.data[j])
        {
            i++;
            j++;
        }
        else 
        {
            j=T.next[j]-1;
        }
    }
    if(j>=T.length) return i-T.length+1;
    else return -1;
}

void myStr::printNext(){
    for(int i = 0; i < length; i++)
        cout << next[i];
    cout << endl;
}

void myStr::printNextVal(){
    for(int i = 0; i < length; i++)
        cout << nextVal[i];
    cout << endl;
}

//初始化稀疏矩阵
myMatrix::myMatrix (const int& rNum, const int& cNum, const int& nNum, const int* data)
{
    rowNum=rNum;
    colNum=cNum;
    nodeNum=nNum;
    if(nNum>0)
    {
        nodeList=new matrixNode[nNum];
        for(int i=0;i<nodeNum;i++)
        {
            nodeList[i].row=data[i*3];
            nodeList[i].col=data[i*3+1];
            nodeList[i].value=data[i*3+2];        
        }
    }
    else
    {
        nodeList=nullptr;
    }
}
myMatrix::myMatrix()
{
    rowNum=0;
    colNum=0;
    nodeNum=0;
    nodeList=nullptr;
}
myMatrix::myMatrix(const myMatrix& other)
{
    rowNum=other.rowNum;
    colNum=other.colNum;
    nodeNum=other.nodeNum;
    if (nodeNum>0) 
    {
        nodeList=new matrixNode[nodeNum];
        for (int i=0; i<nodeNum; i++) 
        {
            nodeList[i]=other.nodeList[i];
        }
    } 
    else 
    {
        nodeList=nullptr;
    }
}

//赋值运算符
myMatrix& myMatrix::operator=(const myMatrix& other) {
    if (this != &other) {
        delete[] nodeList;
        nodeList=nullptr;
        rowNum = other.rowNum;
        colNum = other.colNum;
        nodeNum = other.nodeNum;
        if (nodeNum > 0) {
            nodeList = new matrixNode[nodeNum];
            for (int i = 0; i < nodeNum; i++) {
                nodeList[i] = other.nodeList[i];
            }
        }
    }
    return *this;
}

//析构函数
myMatrix::~myMatrix()
{
    delete[] nodeList;
    nodeList=nullptr;
}

//快速转置算法(转置结果存在T中)
void myMatrix::FastTransposeSMatrix(myMatrix& T)
{
    T.colNum=rowNum;
    T.rowNum=colNum;
    T.nodeNum=nodeNum;
    delete[] T.nodeList;
    T.nodeList = (nodeNum > 0) ? new matrixNode[nodeNum] : nullptr;
    int *num=new int[colNum];
    int *cpot=new int[colNum];
    int col;
    for(col=0;col<colNum;col++)
    {
        num[col]=0;
    }
    for(int t=0;t<nodeNum;t++)
    {
        num[nodeList[t].col]++;
    }
    cpot[0]=0;
    for(col=1;col<colNum;col++)
    {
        cpot[col]=cpot[col-1]+num[col-1];
    }
    for(int p=0;p<nodeNum;p++)
    {
        col=nodeList[p].col;
        int q=cpot[col];
        T.nodeList[q].col=nodeList[p].row;
        T.nodeList[q].row=nodeList[p].col;
        T.nodeList[q].value=nodeList[p].value;
        cpot[col]++;
    }
    delete[] num;
    delete[] cpot;
}

//打印稀疏矩阵
void myMatrix::printMatrix(){
    cout << rowNum << "," << colNum << "," << nodeNum << endl;

    for(int i = 0; i < nodeNum; i++)
        cout << nodeList[i].row << "," << nodeList[i].col << "," << nodeList[i].value << endl;
}
